Complex Brain Networks: A Graph-Theoretical Analysis

233

FIGURE 9.5

Modules and hubs. Modules are shown in dotted regions, central hubs are in

black and gateway hubs are in gray.

to the other nodes as displayed in Figure 9.5 with gateway hubs connecting

different regions and central hubs being the main connection point of the

nodes in a region. Clustering algorithms in brain networks can be classified as

hierarchical, density-based, flow-based and spectral algorithms as we review

in the next sections.

9.4.1.1

Minimum Spanning Tree-based Clustering

Given a weighted and undirected graph G = (V, E), the minimum spanning

tree (MST) of G is a tree T of G that connects all vertices of G and has the

minimum value of 

(u,v)∈T ^{d(u, v) where d(u, v) is the weight associated with}

edge (u, v). Various linear-time algorithms to build MST of a weighted graph

exist including Prim-Jarnik, Kruskal, and Boruvka [6].

MST-based clustering is a popular module detection algorithm to find

clusters in biological networks [6]. An MST of the weighted graph is first

constructed using any algorithm first and the heaviest edge weight is discarded

from the MST at each iteration of the algorithm to form clusters. The main

idea of this algorithm is that the heavy-weight edges have a high probability

of joining clusters.

9.4.1.2

Edge Betweenness-based Clustering

The edge betweenness (EB) analysis of a graph may be used to detect modules

in a brain network as proposed by Newman and Girvan [7] with the idea that

clusters have a high probability of being connected by edges with large edge

betweenness values. The steps of this algorithm may be stated as follows:

1.

Calculate EB values of all edges in the network.

2.

Remove the edge with the highest EB from the network.

3.

Recalculate EB values of the network.

4.

Repeat steps 1-3 until a clustering quality is satisfied.